Problem statement: zenit12kkj
| J: Deľba cukríkov |
| 35 bodov | Časový limit: 200 ms |
Keďže Lukášovi sa po celom tom dni plnom súťaží už nechcelo na tanec ani len pomyslieť,
na párty sa väčšinou venoval konverzácii s inými účastníkmi a konzumácii zaujímavých dobrôt.
Najviac ho oslovili mištičky so zvláštnymi cukríkmi. Mištičiek je veľa a v každej je nejaký
kladný počet chutných cukríkov. Lukáš by najradšej zjedol všetky.
Bohužiaľ, podobnú ambíciu má aj chamtivý Maroško. Napokon sa Lukášovi podarilo dohodnúť,
že sa rozdelia férovo - tak, aby mali obaja rovnako cukríkov. Keďže nechcú presýpať
cukríky medzi mištičkami, môžu si deliť len samotné mištičky.
Maroško trénoval tanec tak veľa, že zabudol všetko ostatné.
Okrem iného aj počítať. V minulosti si ale ako slávny programátor naprogramoval
kalkulačku na mobil a tú teraz používa. Lukáš si všimol, že táto kalkulačka má
dosť závažnú chybu: pri sčítaní zabúda na prenos do vyššieho rádu.
Napríklad sčítanie čísel 13 a 27 vyzerá nasledovne. Najprv si ich kalkulačka zapíše binárne ako
1101 a
11011.
Potom sčíta nasledovne:
01101
11011
-------
10110
Pri sčítaní sa postupuje klasicky sprava doľava. Prvý stĺpec bol sčítaný správne ako 1+1=2. To
znamená, že daná cifra bude 0. Pri správnom postupe by sme si mali zapamätať prenos +1 do vedľajšieho stĺpca, čo ale
Maroškova kalkulačka nerobí.
Takto Maroško dostane výsledok
10110, čo je v desiatkovej sústave 22. Správny výsledok má byť samozrejme
101000 (40). Lukáš vie, že Maroško sa spolieha na svoju kalkulačku a že mu vôbec nepripadá
zvláštne, ak je výsledok sčítania kladných čísel menší ako jeden zo sčítancov.
Ak sa Lukášovi podarí rozdeliť mištičky na dve hromádky tak, že výsledok sčítania počtu cukríkov
na Maroškovej kalkulačke bude rovnaký, potom bude Maroško s daným rozdelením súhlasiť.
Počet mištičiek nemusí byť rovnaký a Maroško musí dostať aspoň jednu.
Pomôžte Lukášovi a zistite, či také rozdelenie existuje a ak áno, koľko najmenej
cukríkov môže byť na Maroškovej hromádke. Maroško počíta súčet postupne: pamätá si medzivýsledok a k nemu
po jednej pripočítava mištičky (zľava doprava v poradí ako na vstupe). Napríklad, ak je mištičiek
šesť a Lukáš si chce nechať druhú a piatu, potom Maroško najprv spočíta súčet prvej a tretej mištičky.
K tomuto súčtu Maroško pripočíta počet cukríkov v štvrtej mištičke a napokon k súčtu týchto troch mištičiek
pripočíta počet cukríkov v šiestej mištičke.
Na prvom riadku vstupu je N (1 ≤ N ≤ 100,000) - počet mištičiek.
Na ďalšom riadku je N medzerou oddelených čísel. Tieto čísla sú celé, kladné a nepresahujú miliardu.
Na jediný riadok výstupu vypíšte
NEDA SA alebo najmenší počet cukríkov, ktoré dostane Maroško.
>
Príklady:
